#!/usr/bin/env python

#
# PISP - A simple Lisp/Scheme like interpreter.
#
# Copyright (c) 2009-2010, Christoph Schunk (schunk _dot_ christoph _at_ googlemail _dot_ com)
# All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are met:
# 1. Redistributions of source code must retain the above copyright
#    notice, this list of conditions and the following disclaimer.
# 2. Redistributions in binary form must reproduce the above copyright
#    notice, this list of conditions and the following disclaimer in the
#    documentation and/or other materials provided with the distribution.
# 3. All advertising materials mentioning features or use of this software
#    must display the following acknowledgement:
#    This product includes software developed by Christoph Schunk.
# 4. Neither the name of Christoph Schunk nor the
#    names of its contributors may be used to endorse or promote products
#    derived from this software without specific prior written permission.
#
# THIS SOFTWARE IS PROVIDED BY CHRISTPH SCHUNK ''AS IS'' AND ANY
# EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
# DISCLAIMED. IN NO EVENT SHALL CHRISTOPH SCHUNK BE LIABLE FOR ANY
# DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
# (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#
# AST
#

class Expression:
    def visit(self, visitor, context):
        pass

class Literal(Expression):
    pass
    
class Value(Literal):
    def __init__(self, value):
        self.value = value

    def __str__(self):
        return str(self.value)

    def visit(self, visitor, context):
        return visitor.visit_value(self, context)

class Symbol(Literal):
    def __init__(self, name):
        self.name = name

    def __str__(self):
        return str(self.name)

    def visit(self, visitor, context):
        return visitor.visit_symbol(self, context)

class List(Expression):
    def __init__(self, *elements):
        self.elements = elements

    def __getitem__(self, i):
        return self.elements[i]

    def __str__(self):
        return "(" + " ".join([str(x) for x in self.elements]) + ")"

    def __len__(self):
        return len(self.elements)

    def head(self):
        return self.elements[0]

    def tail(self):
        return List(*self.elements[1:])

    def is_null(self):
        return len(self.elements) == 0

    def visit(self, visitor, context):
        return visitor.visit_list(self, context)

class ExpressionVisitor:
    def visit_value(self, value, context):
        pass
    
    def visit_symbol(self, symbol, context):
        pass
    
    def visit_list(self, lst, context):
        pass

    def interpret(self, expr, context):
        return expr.visit(self, context)

#
# Scanner
#

class Token:
    def __init__(self, data):
        self.data = data

    #def __str__(self):
    #    return str(self.data)

class SymbolToken(Token):
    def __str__(self):
        return "Symbol: " + str(self.data)

class ValueToken(Token):
    def __str__(self):
        return "Value: " + str(self.data)

class OpenBraceToken(Token):
    def __str__(self):
        return "OpenBrace: " + str(self.data)

class CloseBraceToken(Token):
    def __str__(self):
        return "CloseBrace: " + str(self.data)

class QuoteToken(Token):
    def __str__(self):
        return "Quote: " + str(self.data)

class Scanner:
    def __init__(self, stream):
        self.stream = stream
        self.peek_tvalue = None
        self.peek_value = None

    def next(self):
        if self.peek_value:
            tmp = self.peek_value
            self.peek_value = None
            return tmp
        else:
            return self.stream.read(1)

    def peek(self):
        if not self.peek_value:
            self.peek_value = self.stream.read(1)
        return self.peek_value

    def eof(self):
        return self.peek() == ""
        
    def next_token(self):
        if self.peek_tvalue:
            tmp = self.peek_tvalue
            self.peek_tvalue = None
            return tmp    
        
        while self.peek().isspace():
            self.next()
        
        if self.eof():
            return None
        
        ch = self.next()
        if ch == "(":
            return OpenBraceToken(ch)
        if ch == ")":
            return CloseBraceToken(ch)
        elif ch == "'":
            return QuoteToken(ch)
        elif ch.isdigit():
            tok = ch
            while self.peek().isdigit():
                tok = tok + self.next()
            if self.peek() in "()' " or self.eof():
                return ValueToken(int(tok))
            if self.peek() != ".":
                raise Exception()
            tok = tok + "."
            while self.peek().isdigit():
                tok = tok + self.next()
            if self.peek() in "()'" or self.eof():
                return ValueToken(float(tok))
            else:
                raise Exception()
        elif ch.isalpha() or ch in "+-/%*=_<>":
            tok = ch
            while self.peek().isalnum() or self.peek() in "+-/%*=_<>":
                tok = tok + self.next()
            return SymbolToken(tok)
        else:
            raise Exception(ch)

    def peek_token(self):
        if not self.peek_tvalue:
            self.peek_tvalue = self.next_token()
        return self.peek_tvalue

#
# Parser
#

class Parser:
    def __init__(self, scanner):
        self.scanner = scanner

    def parse_program(self):
        program = []
        while s.peek_token():
            program.append(self.parse())
        return program

    def parse(self):
        tok = self.scanner.next_token()
        #print tok
        if tok == None:
            return None
        if isinstance(tok, OpenBraceToken):
            #print "list:", tok
            l = []
            while not isinstance(self.scanner.peek_token(), CloseBraceToken) and self.scanner.peek_token() != None:
                l.append(self.parse())
            if not isinstance(self.scanner.next_token(), CloseBraceToken):
                raise Exception(tok)
            #print ")"
            return List(*l)
        else:
            if isinstance(tok, SymbolToken):
                #print "sym:", tok
                return Symbol(tok.data)
            elif isinstance(tok, ValueToken):
                #print "val:", tok
                return Value(tok.data)
            else:
                raise Exception(tok)
        
#
# Interpreter
#

class Environment:
    def __init__(self, parent = None, bindings = {}):
        self.parent = parent
        self.bindings = bindings

    def lookup(self, name):
        if name in self.bindings:
            return self.bindings[name]
        if self.parent == None:
            raise Exception("Interpreter error: " + str(name) + " not defined.")
        return self.parent.lookup(name)

    def bind(self, name, value):
        self.bindings[name] = value

    def __str__(self):
        return str(self.bindings)

class Function:
    def __init__(self, func = None, param = None, body = None):
        self.param = param
        self.body = body
        self.func = func

    def call(self, tail, env, interp):
        if self.func: # builtin method: do lazy evaluation
            return self.func(tail, env, interp)
        else:         # user defined method: do eager evaluation
            assert len(self.param) == len(tail)
            parameter_values = map(lambda x: x.visit(interp, env), tail)
            #print "val:", parameter_values, self.param
            new_env = Environment(env, dict(zip(self.param, parameter_values)))
            return self.body.visit(interp, new_env)
            
class InterpreterVisitor(ExpressionVisitor):
    def visit_symbol(self, symbol, env):
        return env.lookup(symbol.name)

    def visit_value(self, value, env):
        return value.value

    def visit_list(self, lst, env):
        if lst.is_null():
            raise Exception()
        func = lst.head().visit(self, env)
        #print "visit_list:", lst.tail()
        if not isinstance(func, Function):
            raise Exception("Function expected but " + str(func) + "found")
        return func.call(lst.tail(), env, self)

#
# RTL
#

def plus_builtin(l, env, inter):
    return reduce(lambda x, y: x + y.visit(inter, env), l, 0)

def minus_builtin(l, env, inter):
    return l[0].visit(inter, env) - l[1].visit(inter, env) #reduce(lambda x, y: x - y.visit(inter, env), l, 0)

def mul_builtin(l, env, inter):
    return reduce(lambda x, y: x * y.visit(inter, env), l, 1)

def lambda_builtin(l, c, inter):
    assert len(l) == 2
    assert reduce(lambda x, y: x and isinstance(y, Symbol), l[0], True)
    return Function(None, map(lambda x: x.name, l[0]), l[1]);

def define_builtin(l, env, interp):
    assert len(l) == 2
    assert isinstance(l[0], Symbol)
    env.bind(l[0].name, l[1].visit(interp, env))
    return None

def quote_builtin(l, env, interp):
    assert len(l) == 1
    #print "quote:", l.head()
    return l.head()

def car_builtin(l, env, interp):
    assert len(l) == 1
    v = l.head().visit(interp, env)
    return v.head()

def cdr_builtin(l, env, interp):
    assert len(l) == 1
    v = l.head().visit(interp, env)
    return v.tail()

def if_builtin(l, env, interp):
    assert len(l) > 1 and len(l) < 4
    if len(l) == 2:
        if l[0].visit(interp, env):
            return l[1].visit(interp, env)
        else:
            return None
    else:
        if l[0].visit(interp, env):
            return l[1].visit(interp, env)
        else:
            return l[2].visit(interp, env)

def le_builtin(l, env, interp):
    assert len(l) == 2
    v = l[0].visit(interp, env) < l[1].visit(interp, env)
    return v
        

#
# Test 
#

def evl(v, env, i):
    print v
    r = i.interpret(v, env)
    print ">", r

i = InterpreterVisitor()
c = Environment()
c.bind("+", Function(plus_builtin))
c.bind("-", Function(minus_builtin))
c.bind("*", Function(mul_builtin))
c.bind("lambda", Function(lambda_builtin))
c.bind("define", Function(define_builtin))
c.bind("car", Function(car_builtin))
c.bind("cdr", Function(cdr_builtin))
c.bind("quote", Function(quote_builtin))
c.bind("if", Function(if_builtin))
c.bind("<", Function(le_builtin))

s = Scanner(open("test.pisp"))
p = Parser(s)
e = p.parse_program()
for ins in e:
    evl(ins, c, i)

"""
i1 = List([Symbol("define"), Symbol("t"), Value(5)])
i2 = List([Symbol("+"), Value(1), Value(2), Value(3), Symbol("t")])
i3 = List([Symbol("lambda"), List([Symbol("a")]),
              List([Symbol("+"), Symbol("a"), Value(1)])])
i4 = List([Symbol("define"), Symbol("succ"), i3])
i5 = List([Symbol("succ"), Value(5)])

#evl(List(Symbol("quote"), List(1, 2, 3)), c, i)
i6 = List(Symbol("cdr"), List(Symbol("quote"), List(1, 2, 3)))
#evl(i6, c, i)

i6 = List([Symbol("quote"),List([1, 2, 3]) ])
#evl(i6, c, i)
i6 = List([Symbol("cdr"),  List([ Symbol("quote"), List([1, 2, 3])]) ])
#evl(i6, c, i)
"""
